package org.example.leetCode;

/**
 * 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * 从后往前
 */
public class Code14 {
    public static void main(String[] args) {
        String[] strs = {"flower", "flow", "flight"};
        System.out.println(longestCommonPrefix(strs)); // 输出: "fl"
    }

    /**
     * 查找字符串数组中的最长公共前缀
     *
     * @param strs 字符串数组
     * @return 最长公共前缀
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return ""; // 如果数组为空或长度为0，返回空字符串
        }

        // 假设第一个字符串为公共前缀
        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            // 不断缩短prefix，直到它是当前字符串的前缀
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1); // 删除最后一个字符
                if (prefix.isEmpty()) {
                    return ""; // 如果prefix为空，说明没有公共前缀
                }
            }
        }

        return prefix; // 返回最长公共前缀
    }
}
